package m202405.d18;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/18 14:11
 */
public class Q763 {

    public static void main(String[] args) {
        Q763 q763 = new Q763();
        List<Integer> list = q763.partitionLabels("aaa");
        System.out.println();
    }

    public List<Integer> partitionLabels(String s) {
        int[] indexes = new int['z' - 'a' + 1];
        Arrays.fill(indexes, -1);
        for (int i = s.length() - 1; i >= 0; i--) {
            int p = s.charAt(i) - 'a';
            if (indexes[p] > 0) {
                continue;
            }
            indexes[s.charAt(i) - 'a'] = i;
        }
        List<Integer> res = new ArrayList<>();
        int end = 0;
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int index = indexes[c - 'a'];
            if (index > i) {
                end = Math.max(index, end);
                continue;
            }
            if (i >= end) {
                res.add(end - start + 1);
                start = i + 1;
                end = start;
            }
        }
        return res;
    }

    public List<Integer> partitionLabels1(String s) {
        List<Integer> res = new ArrayList<>();
        int end = 0;
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int next = find(s, i + 1, c);
            if (next > 0) {
                end = Math.max(next, end);
                continue;
            }
            if (i >= end) {
                res.add(end - start + 1);
                start = i + 1;
                end = start;
            }
        }
        return res;
    }

    private int find(String s, int start, char c) {
        for (int i = s.length() - 1; i >= start; i--) {
            if (c == s.charAt(i)) {
                return i;
            }
        }
        return -1;
    }
}
